package com.gitee.ywj1352.算法.week01;


import java.util.*;

/**
 * 给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。
 * <p>
 * 初始化nums1 和 nums2 的元素数量分别为m 和 n 。你可以假设nums1有足够的空间（空间大小等于m + n）来保存 nums2 中的元素。
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MergeArray {


    //最大的问题 为什么 非要 从前开始排  从后开始不是一样的吗？？

    /**
     * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     * 输出：[1,2,2,3,5,6]
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        //可以去除
        int hou, qian, temp;
        for (int i = 0; i < m; i++) {
            hou = nums1.length - i - 1;
            qian = m - i - 1;
            temp = nums1[hou];
            nums1[hou] = nums1[qian];
            nums1[qian] = temp;
        }

        int i = 0;
        int a = n, b = 0;
        for (; a < nums1.length && b < n; i++) {
            if (nums1[a] < nums2[b]) {
                nums1[i] = nums1[a];
                a++;
            } else {
                nums1[i] = nums2[b];
                b++;
            }
        }
        if (b == nums2.length - 1) {
            for (; a < nums1.length; a++, i++) {
                nums1[i] = nums1[a];
            }
        }
        if (a == nums1.length) {
            for (; b < nums2.length; b++, i++) {
                nums1[i] = nums2[b];
            }
        }
    }

    /**
     * nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merge(nums1, 3, nums2, 3);

        System.out.println(Arrays.toString(nums1));


    }


}
